#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <string.h>
#include <MyString.h>
#define ElementType void*

struct Student
{
    int id;
    MyStr name;
    int age;
};
typedef struct Student Stu;

Stu * CreateStu(const int id,const char *name,const int age)
{
    Stu *s = (Stu *)malloc(sizeof(Stu));
    if(s == NULL)
    {
        return NULL;
    }
    s->id = id;
    s->age = age;
    s->name = GetString(name);
    return s;
}

void ClearStu(void *ptr)
{
    Stu *s = (Stu *)ptr;
    //printf("释放学生对象%s\n",s->name.string);
    ClearString(&s->name);
    free(s);
}

void PrintStu(void *ptr)
{
    Stu *s = (Stu *)ptr;
    printf("学生学号:%d 学生姓名:%s 学生年龄:%d\n",s->id,s->name.string,s->age);
}

bool SortByAge(void *ptr1, void *ptr2)
{
    Stu *s1 = (Stu*)ptr1;
    Stu *s2 = (Stu*)ptr2;
    if(s1->age < s2->age)
    return true;
    return false;
}

bool SortByName(void *ptr1,void *ptr2)
{
    Stu *s1 = (Stu*)ptr1;
    Stu *s2 = (Stu*)ptr2;
    if(strcmp(s1->name.string , s2->name.string) > 0)
    return true;
    return false;
}

bool SortById(void *ptr1, void *ptr2)
{
    Stu *s1 = (Stu*)ptr1;
    Stu *s2 = (Stu*)ptr2;
    if(s1->id > s2->id)
        return true;
    return false;
}



//节点
struct Node
{
    //数据域
    ElementType data;
    //指针域
    struct Node * next;
};

//链表结构体
struct LinkList
{
    //头节点指针
    struct Node* head;
    //链表长度
    int len;
};
typedef struct LinkList Llist;

//创建节点的接口
struct Node* CreateNode(ElementType element)
{
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode == NULL)
    {
        printf("create node malloc error!\n");
        return NULL;
    }
    newNode->data = element;
    newNode->next = NULL;
    return newNode;
}

//初始化链表
void InitLlist(Llist *l)
{
    //创建一个头节点
    l->head = CreateNode(0);
    l->len = 0;
}

//尾插法
void InsertLlistTail(Llist *l,ElementType element)
{
    //遍历指针
    struct Node *TravelPoint = l->head;
    //这个节点不是尾巴
    while(TravelPoint->next != NULL)
    {
        TravelPoint = TravelPoint->next;
    }

    TravelPoint->next = CreateNode(element);
    l->len++;
}

//头插法
void InsertLlistHead(Llist *l,ElementType element)
{
    struct Node *newNode = CreateNode(element);
    newNode->next = l->head->next;
    l->head->next = newNode;
    l->len++;
}

//中间插
void InsertLlistByIndex(Llist *l,ElementType element,int index)
{
    if(index < 0 || index > l->len)
    {
        printf("插入位置非法:%d len : %d\n",index,l->len);
        return;
    }
    //TravelPoint停在要插入的前一个位置
    struct Node *TravelPoint = l->head;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    struct Node *newNode = CreateNode(element);
    newNode->next = TravelPoint->next;
    TravelPoint->next = newNode;
    l->len++;
}

//按位置删除
void RemoveByIndex(Llist *l,int index)
{
    if(index < 0 || index >= l->len)
    {
        printf("删除位置非法:%d len : %d\n",index,l->len);
        return;
    }
    //TravelPoint停在要删除的前一个位置
    struct Node *TravelPoint = l->head;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    struct Node *freeNode = TravelPoint->next;
    TravelPoint->next = freeNode->next;
    free(freeNode);
    l->len--;
}

//按值删除
void RemoveByElement(Llist *l,ElementType element)
{
    struct Node *TravelPoint = l->head;
    while(TravelPoint->next != NULL)
    {
        //travelpoint的下一个节点需要删除
        if(TravelPoint->next->data == element)
        {
            //留下这块内存的地址，后续释放，防止内存泄漏
            struct Node *freeNode = TravelPoint->next;
            TravelPoint->next = freeNode->next;
            free(freeNode);
            l->len--;
        }
        else
        {
            //避免要删除的两个相邻的值相等
            TravelPoint = TravelPoint->next;
        }
    }
}

//按位置改
void UpdateByIndex(Llist *l,int index,ElementType newValue)
{
    if(index < 0 || index >= l->len)
    {
        printf("位置非法的修改:%d len : %d\n",index,l->len);
        return;
    }
    struct Node *TravelPoint = l->head->next;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    TravelPoint->data = newValue;
}

//按值修改
void UpdateByElement(Llist *l,ElementType oldValue,ElementType newValue)
{
    struct Node *TravelPoint = l->head;
    while(TravelPoint->next != NULL)
    {
        //travelpoint的下一个节点需要删除
        if(TravelPoint->next->data == oldValue)
        {
            TravelPoint->next->data = newValue;
        }
        TravelPoint = TravelPoint->next;
    }
}

//按位置查找
ElementType* FindByIndex(Llist *l,int index)
{
    if(index < 0 || index >= l->len)
    {
        printf("位置非法的查找:%d len : %d\n",index,l->len);
        return NULL;
    }
    struct Node *TravelPoint = l->head->next;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    return &TravelPoint->data;
}

//按值查找    返回值：结点指针的数列
struct Node** FindByElement(Llist *l,ElementType element)
{
    //指针数组,dyA指向指针数组的指针，用二级指针
    //len个指针的空间+1：多一个位置放结束符NULL
    struct Node **dyA = (struct Node**)malloc(sizeof(struct Node*) * (l->len + 1));
    if(dyA == NULL)
    {
        printf("malloc error!\n");
        return NULL;
    }
    int count = 0;
    struct Node *TravelPoint = l->head;
    while(TravelPoint->next != NULL)
    {
        //travelpoint的下一个节点需要删除
        if(TravelPoint->next->data == element)
        {
            //把符合条件的结点指针放入数组
            dyA[count] = TravelPoint ->next;
            count++;
        }
        TravelPoint = TravelPoint->next;
    }
    //放上结束符号
    dyA[count] = NULL;
    //返回指针
    return dyA;
}

//遍历
void Travel(Llist *l,void (*funcPtr)(void*))
{
    printf("len : %d\n",l->len);
    printf("===========================================================\n");
    //头节点不参与遍历操作
    struct Node* TravelPoint = l->head->next;
    while(TravelPoint != NULL)
    {
        funcPtr(TravelPoint->data);
        //走向下一个节点
        TravelPoint = TravelPoint->next;
    }
    printf("\n");
    printf("===========================================================\n");
}

//交换
void Swap(ElementType *value1,ElementType *value2)
{
    ElementType temp = *value1;
    *value1 = *value2;
    *value2 = temp;
}

//排序
void FastSort(struct Node *start,struct Node *end,bool (*funcPtr)(void*,void *))
{
    if(start == end)
    {
        return;
    }

    struct Node *p1 = start;
    struct Node *p2 = p1->next;

    //循环终止条件
    while(p2 != end)
    {
        //后面的指针的值比基准值小
        if(funcPtr(p2->data,start->data) == true)
        {
            //p1向后移动,把p1和p2的值交换
            p1 = p1->next;
            Swap(&p1->data,&p2->data);
        }
        //交换完后,p2继续向后移动
        p2 = p2->next;
    }
    //最后将基准值和p1交换,p1之前的值都比p1小,p2之后的值都比p2大
    Swap(&start->data,&p1->data);
    //经过一轮排序,p1的位置一定在比它小的值末尾,p2一定在比它大的值的末尾
    FastSort(start,p1,funcPtr);
    FastSort(p1->next,p2,funcPtr);
}

//单链表的逆序
void Reserve(Llist *l)
{
    if(l->len == 0 || l->len == 1)
        return;
    //前驱节点
    struct Node*prev = NULL;
    //所需逆序的节点
    struct Node *cur = l->head->next;
    //后驱节点
    struct Node *Next = cur->next;

    while(Next != NULL)
    {
        cur->next = prev;
        //谁没用谁先走
        prev = cur;
        cur = Next;
        Next = cur->next;
    }
    //最后一个Next为NULL情况还没有逆序
    cur->next = prev;
    l->head->next = cur;
}

//递归逆序
struct Node *Reserve2(struct Node *node)
{
    //递归的终止条件
    if(node->next == NULL)
    {
        return node;
    }
    else
    {
        struct Node *tail = Reserve2(node->next);
        node->next->next = node;
        node->next = NULL;
        return tail;
    }
}

//归并
Llist Merge(Llist *l1,Llist *l2)
{
    Llist list;
    InitLlist(&list);
    struct Node *p1 = l1->head->next;
    struct Node *p2 = l2->head->next;
    while(p1 != NULL && p2 != NULL)
    {
        if(p1->data > p2->data)
        {
            InsertLlistTail(&list,p2->data);
            p2 = p2->next;
        }
        else
        {
            InsertLlistTail(&list,p1->data);
            p1 = p1->next;
        }
    }
    while(p1 != NULL)
    {
        InsertLlistTail(&list,p1->data);
        p1 = p1->next;
    }
    while(p2 != NULL)
    {
        InsertLlistTail(&list,p2->data);
        p2 = p2->next;
    }
    return list;
}

//释放链表(从前往后释放)
void FreeLlist(Llist *l)
{
    while(l->head != NULL)
    {
        struct Node* next = l->head->next;
        free(l->head);
        l->head = next;
    }
    
    l->len = 0;
}

int main()
{
    // Llist l;
    // //撒下随机种子
    // srand(time(NULL));
    // InitLlist(&l);
    // for(int i = 1; i <= 10; i++)
    // {
    //     InsertLlistTail(&l,rand()%100);
    // }
    // FastSort(l.head->next,NULL);
    // Travel(&l);
    
    // Llist l2;
    // //撒下随机种子
    // srand(time(NULL));
    // InitLlist(&l2);
    // for(int i = 1; i <= 10; i++)
    // {
    //     InsertLlistTail(&l,rand()%100);
    // }
    // // InsertLlistHead(&l,100);
    // // InsertLlistHead(&l,100);
    // // InsertLlistByIndex(&l,23,3);
    // // RemoveByIndex(&l,2);
    // // RemoveByElement(&l,100);
    // // UpdateByIndex(&l,1,24);
    // // UpdateByElement(&l,10,34);
    // //Travel(&l2);
    // FastSort(l2.head->next,NULL);
    // Travel(&l);
    // //l.head->next = Reserve2(l.head->next);
    // //Travel(&l);

    // // int *ptr = FindByIndex(&l,1);
    // // if(ptr == NULL)
    // //     printf("没找到!\n");
    // // else printf("node element : %d\n",*ptr);

    // // struct Node** dyA = FindByElement(&l,24);
    // // int count = 0;
    // // while(dyA[count] != NULL)
    // // {
    // //     printf("node element : %d\n",dyA[count]->data);
    // //     count++;
    // // }
    // // free(dyA);
    // Llist list = Merge(&l,&l2);
    // FastSort(list.head->next,NULL);
    // Travel(&list);

    // FreeLlist(&l);
    // FreeLlist(&l2);
    // return 0;



    Llist list;
    InitLlist(&list);
    InsertLlistTail(&list,CreateStu(1,"zhangsan",20));
    InsertLlistTail(&list,CreateStu(2,"lisi",22));
    InsertLlistTail(&list,CreateStu(3,"wangwu",21));

    FastSort(list.head->next,NULL,SortByAge);

    Travel(&list,PrintStu);
    return 0;
}